package cn.edu.besti.cs1723.Z2316;

public class Searching<T extends Comparable<? super T>> {


    int max_size = 20;//斐波那契数组的长度

    public Searching() {

    }

    public boolean LinearSearch(T[] data, int min, int max, T target) {
        int index = min;
        boolean found = false;

        while (!found && index <= max) {
            if (data[index].compareTo(target) == 0)
                found = true;
            index++;
        }
        return found;
    }

    //二分查找（折半查找），版本1
    public int BinarySearch1(int a[], int value, int n)
    {
        int low, high, mid;
        low = 0;
        high = n - 1;
        while(low <= high)
        {
            mid = (low + high) / 2;
            if(a[mid] == value)
                return mid;
            if(a[mid] > value)
                high = mid - 1;
            if(a[mid] < value)
                low = mid + 1;
        }
        return -1;
    }

    //二分查找，递归版本
    public int BinarySearch2(int a[], int value, int low, int high)
    {
        int mid = low + (high - low) / 2;
        if(a[mid] == value)
            return mid;
        if(a[mid] > value)
            return BinarySearch2(a, value, low, mid - 1);
        if(a[mid] < value)
            return BinarySearch2(a, value, mid + 1, high);
        return -1;
    }

    //插值查找
    public int InsertionSearch(int a[], int value, int low, int high)
    {
        int mid = low + (value - a[low]) / (a[high] - a[low]) * (high - low);
        if(a[mid] == value)
            return mid;
        if(a[mid] > value)
            return InsertionSearch(a, value, low, mid - 1);
        if(a[mid] < value)
            return InsertionSearch(a, value, mid + 1, high);
        return -1;
    }


    /*构造一个斐波那契数组*/
    public int[] Fibonacci()
    {
        int[] F = new int[max_size];
        F[0] = 0;
        F[1] = 1;
        for(int i = 2;i < max_size;++i)
            F[i] = F[i - 1]+F[i - 2];
        return F;
    }

    /*定义斐波那契查找法*/
    public int FibonacciSearch(int[] a, int n, int key)  //a为要查找的数组,n为要查找的数组长度,key为要查找的关键字
    {
        int low = 0;
        int high = n - 1;

        int[] F = Fibonacci();//构造一个斐波那契数组F

        int k = 0;
        while(n > F[k] - 1)//计算n位于斐波那契数列的位置
            ++k;

        int[] temp;//将数组a扩展到F[k]-1的长度
        temp = new int [F[k] - 1];
        int[] a2 = new int[F[k] - 1];
        for (int i = 0; i < a.length; i++) {
            a2[i] = a[i];
        }

        for(int i = n; i < F[k] - 1; ++i)
            temp[i]=a2[n - 1];

        while(low <= high)
        {
            int mid = low + F[k - 1] - 1;
            if(key < temp[mid])
            {
                high = mid - 1;
                k--;
            }
            else if(key > temp[mid])
            {
                low = mid + 1;
                k -= 2;
            }
            else
            {
                if(mid < n)
                    return mid; //若相等则说明mid即为查找到的位置
                else
                    return n - 1; //若mid>=n则说明是扩展的数值,返回n-1
            }
        }

        return -1;
    }





}
